#pragma once
#include <cstdlib>
#include <iostream>
#include <vector>

class UnionFindSet
{
    private:
        std::vector<int> _v;
    public:
        UnionFindSet(size_t n): _v(n,-1){}
        //合并
    void Union(int x1 , int x2)
    {
        int root1 = FindRoot(x1);
        int root2 = FindRoot(x2);
        if(root1 == root2) return;
        if(x1 > x2) std::swap(x1,x2);
        _v[root1]+= _v[root2];
        _v[root2] = root1;
    }
        //返回集合个数
    int SizeOfSet()
    {
        int counts = 0;
        for(size_t i = 0 ; i < _v.size() ; ++ i)
        {
            if(_v[i] < 0){
                ++counts;
            }
        }
        return counts;
    }
        //找根
    int FindRoot(int x)
    {
        auto root = x;
        while(_v[root] >= 0)
        {
            root = _v[root];
        }
        //路径压缩
        while(_v[x] >= 0)
        {
            int parent = _v[x];
            _v[x] = root;
            x = parent;
        }
        return root;
    }

};